1. Field of the Invention
The present invention relates to programmable logic arrays, and in particular, to structures and techniques for improving carry propagation in programmable logic arrays.
2. Description of the Related Art
Techniques for implementing carry propagation in commercially prevalent programmable logic devices (PLDs) or arrays (PLAs) aim at fast carry propagation. FIG. 1 illustrates a configurable logic block (CLB) of a conventional PLD or PLA made by Xilinx, Inc. This CLB is described in more detail in U.S. Pat. No. 5,546,018. As shown, the Xilinx CLB includes four four-input function generator F, G, H, J each comprising lookup tables for implementing one bit of an arithmetic function of two variables which are received on the input terminals 0, 1, 2, 3 of each function generator. Associated with each function generator is a fast carry mux C1, C2, C3, C4. The purpose of these muxes is to propagate carry based on the logical input CIN and the result of the arithmetic function between input variables A and B so as to provide a cumulative carry output signal COUT.
In the conventional PLD described above, for multibit operations of two variables greater than four bits, the carry output signal of one CLB is provided to the carry input of a higher-order CLB in a chain of CLBs depending on the number of bits desired. It should be noted that in the CLB illustrated in FIG. 1, a sum output stage is provided in another CLB for finalizing the sum values using the outputs of the CLB in FIG. 1.
FIG. 2 illustrates a logic array block (LAB) of a conventional PLD made by Altera, Inc. This LAB is described in more detail in U.S. Pat. No. 5,761,099. In this device, each logic element 12 (typically eight or ten per LAB) can be configured to perform one bit of an arithmetic operation of two input variables. Each logic element 12 further includes logic 13 for providing a carry output signal based on a carry input and the arithmetic operation of two variables. As shown in FIG. 2, carry is propagated between logic elements along lines 70a in ripple fashion as in the Xilinx device. Lines 70b provide for multibit operations of two variables greater than the number of bits capable of being processed by a single LAB. In such circumstances, the xe2x80x9cdirect carry outxe2x80x9d signal of one LAB is provided to the xe2x80x9cdirect carry inxe2x80x9d signal of a higher-order LAB in a chain of LABs depending on the number of bits desired.
The conventional ripple carry propagation technique described above is slow because the highest order output is not valid until a carry has rippled through all the lower order bits.
Carry lookahead techniques offer the promise of much faster carry propagation than can be achieved with ripple carry techniques. Such techniques have been implemented in digital arithmetic structures for decades (e.g. the 74182 look-ahead carry generator). See, for example, Joseph D. Greenfield, Practical Digital Design Using ICs, xc2xa714.11 (1983). Some theoretical discussions have addressed considerations for extending such techniques to programmable gate arrays. See, for example, Charle R. Rupp, xe2x80x9cFast Algorithms for Regular Functions in Field Programmable Gate Arrays,xe2x80x9d Proceedings of the Third Annual PLD Conference (1993). However, prior art structures for performing carry lookahead features require a prohibitive number of elements and complex interconnections therebetween that are not suitable for implementation in a PLD or PLA. Accordingly, carry lookahead techniques have not been seriously considered for use in conventional programmable logic devices.
What is needed in the art, therefore, is an improved carry propagation technique that is suitable for implementation in a programmable logic device. The present invention fulfills this need, among others.
Accordingly, it is an object of the present invention to overcome the above-described problems in the prior art.
Another object of the invention is to improve the speed of operations in a programmable logic device.
Another object of the invention is to improve the speed of operations that require carry propagation in a programmable logic device.
Another object of the invention is to provide improved performance in a programmable logic device with minimal additional structure.
Another object of the invention is to minimize the number of interconnections required to implement carry propagation techniques in a programmable logic device.
Another object of the invention is to provide a carry lookahead technique that is suitable for implementation in a programmable logic device.
These and other objects are fulfilled by the present invention, in which carry lookahead techniques are adapted for use in a programmable logic device. In one example of the invention, a carry result is computed for a block of function cells, each function cell representing one bit in a multibit operation that uses carry. This carry result is combined with the carry input from a function cell block representing less significant bits in the operation and a carry output is provided to a function cell block representing more significant bits in the operation. The received carry can also be supplied to adjust provisional carry results for each bit associated with the function cells in the block. Accordingly, the received carry input need not be rippled through all the function cells in the block, thus reducing carry propagation delays. This technique is suitable for use in programmable logic devices because only minimal additional logic need be included in each block of function cells (such as the CLBs and LABs in the prior art), and because few, in any, new interconnections between blocks need be introduced.